#include <dbg.h>
#include <gtest/gtest.h>

using std::string;
using std::vector;

static const vector<string> MAPPING{
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    static vector<string> letterCombinations(const string& digits) {
        if (digits.empty()) {
            return {};
        }

        vector<string> res{};
        string path;
        dfs(0, path, digits, res);

        return res;
    }

private:
    static void dfs(int index,
                    string& path,
                    const string& digits,
                    vector<string>& res) {
        if (index == digits.size()) {
            res.push_back(path);
            return;
        }

        for (const char c : MAPPING[digits[index] - '0']) {
            path.push_back(c);
            dfs(index + 1, path, digits, res);
            path.pop_back();
        }
    }
};

TEST(TEST1, letterCombinations) {
    Solution s;
    const string digits{"23"};
    const vector<string> res{
        "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"};
    EXPECT_EQ(s.letterCombinations(digits), res);
}

TEST(TEST2, letterCombinations) {
    Solution s;
    const string digits;
    const vector<string> res{};
    EXPECT_EQ(s.letterCombinations(digits), res);
}

TEST(TEST3, letterCombinations) {
    Solution s;
    const string digits{"2"};
    const vector<string> res{"a", "b", "c"};
    EXPECT_EQ(s.letterCombinations(digits), res);
}

int main(int argc, char** argv) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}